package com.lw.leetcode.binary;

/**
 * @Author liw
 * @Date 2021/4/21 10:34
 * @Version 1.0
 */
public class Search {

    public static void main(String[] args) {
        Search search = new Search();
//        int[] nums = {2,5,6,0,0,1,2};
//        int[] nums = {4,5,6,7,0,1,2};
        // [1,0,1,1,1]
        // [1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1]
//        int[] nums = {1,0,1,1,1};
//        int[] nums = {2,3,4,5,6,7,1};
//        int[] nums = {1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1};
        int[] nums = {15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14};

//        int aa = getStartIndex(nums);
//        System.out.println(aa);

        for (int i = 0; i < 1; i++) {
            int search1 = search.search(nums, 5);
            System.out.println(i + "     " + search1);
        }
    }
// [1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1]
//2

    private int findMin(int[] nums) {
        int st = 0;
        int end = nums.length - 1;
        while (st < end) {
            int last = nums[end];
            int m = st + ((end - st) >>> 1);
            if (nums[m] > last) {
                st = m + 1;
            } else if (nums[m] < last) {
                end = m;
            } else {
                for (int i = st; i <= end; i++) {
                    if (i != 0 && nums[i - 1] > nums[i]) {
                        return i;
                    }
                }
                return st;
            }
        }
        return st;
    }

    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        if (nums[0] == target) {
            return 0;
        }
        int index = findMin(nums);
        System.out.println(index);
        int length = nums.length;
        int st = 0;
        int end = length - 1;
        while (st < end) {
            int m = st + ((end - st) >> 1);
            int v = m + index;
            int m1 = v >= length ? v - length : v;
            if (nums[m1] < target) {
                st = m + 1;
            } else {
                end = m;
            }
        }
        st = st + index >= length ? st + index - length : st + index;
        if (nums[st] == target) {
            return st;
        }
        return -1;
    }

}
